﻿<!DOCTYPE html>
<html>
<head>  <meta charset="utf-8">
  <meta name="viewport" content="width=device-width,height=device-height,initial-scale=1,user-scalable=0">
  <meta name="author" content="微信公众号：颜家大少">
  <meta name="email" content="3056432@qq.com">
  <meta name="description" content="一个Markdown在线转换工具，让Markdown内容，不需作任何调整就能同时在微信公众号、博客园、掘金、csdn等平台正确显示当前预览的效果">
  <title>Md2All export document</title>  
  <style type="text/css" id="markdown_preview_css"> 
 .output_wrapper pre code{font-family: Consolas, Inconsolata, Courier, monospace; display: block !important; white-space: pre !important; word-wrap: normal !important; word-break: normal !important;  overflow: auto !important;}  
.output_wrapper a:hover { text-decoration: underline; color: rgb(0, 96, 100); }
.output_wrapper figcaption { margin-top: 10px; text-align: center; color: rgb(153, 153, 153); font-size: 0.7em; }
.output_wrapper pre code .linenum { padding-right: 20px; word-spacing: 0px; }
.task-list-list { list-style-type: none; }
.task-list-list.checked { color: rgb(62, 62, 62); }
.task-list-list.uncheck { color: rgb(191, 193, 191); }
.task-list-list .icon_uncheck, .task-list-list .icon_check { display: inline-block; vertical-align: middle; margin-right: 10px; }
.task-list-list .icon_check::before { content: "√"; border: 2px solid rgb(62, 62, 62); color: red; }
.task-list-list .icon_uncheck::before { content: "x"; border: 2px solid rgb(191, 193, 191); color: rgb(191, 193, 191); }
.task-list-list .icon_check::before, .task-list-list .icon_uncheck::before { padding: 2px 8px 2px 5px; border-radius: 5px; }
@font-face { font-family: KaTeX_AMS; src: url("fonts/KaTeX_AMS-Regular.woff2") format("woff2"), url("fonts/KaTeX_AMS-Regular.woff") format("woff"), url("fonts/KaTeX_AMS-Regular.ttf") format("truetype"); font-weight: normal; font-style: normal; }
@font-face { font-family: KaTeX_Caligraphic; src: url("fonts/KaTeX_Caligraphic-Bold.woff2") format("woff2"), url("fonts/KaTeX_Caligraphic-Bold.woff") format("woff"), url("fonts/KaTeX_Caligraphic-Bold.ttf") format("truetype"); font-weight: bold; font-style: normal; }
@font-face { font-family: KaTeX_Caligraphic; src: url("fonts/KaTeX_Caligraphic-Regular.woff2") format("woff2"), url("fonts/KaTeX_Caligraphic-Regular.woff") format("woff"), url("fonts/KaTeX_Caligraphic-Regular.ttf") format("truetype"); font-weight: normal; font-style: normal; }
@font-face { font-family: KaTeX_Fraktur; src: url("fonts/KaTeX_Fraktur-Bold.woff2") format("woff2"), url("fonts/KaTeX_Fraktur-Bold.woff") format("woff"), url("fonts/KaTeX_Fraktur-Bold.ttf") format("truetype"); font-weight: bold; font-style: normal; }
@font-face { font-family: KaTeX_Fraktur; src: url("fonts/KaTeX_Fraktur-Regular.woff2") format("woff2"), url("fonts/KaTeX_Fraktur-Regular.woff") format("woff"), url("fonts/KaTeX_Fraktur-Regular.ttf") format("truetype"); font-weight: normal; font-style: normal; }
@font-face { font-family: KaTeX_Main; src: url("fonts/KaTeX_Main-Bold.woff2") format("woff2"), url("fonts/KaTeX_Main-Bold.woff") format("woff"), url("fonts/KaTeX_Main-Bold.ttf") format("truetype"); font-weight: bold; font-style: normal; }
@font-face { font-family: KaTeX_Main; src: url("fonts/KaTeX_Main-BoldItalic.woff2") format("woff2"), url("fonts/KaTeX_Main-BoldItalic.woff") format("woff"), url("fonts/KaTeX_Main-BoldItalic.ttf") format("truetype"); font-weight: bold; font-style: italic; }
@font-face { font-family: KaTeX_Main; src: url("fonts/KaTeX_Main-Italic.woff2") format("woff2"), url("fonts/KaTeX_Main-Italic.woff") format("woff"), url("fonts/KaTeX_Main-Italic.ttf") format("truetype"); font-weight: normal; font-style: italic; }
@font-face { font-family: KaTeX_Main; src: url("fonts/KaTeX_Main-Regular.woff2") format("woff2"), url("fonts/KaTeX_Main-Regular.woff") format("woff"), url("fonts/KaTeX_Main-Regular.ttf") format("truetype"); font-weight: normal; font-style: normal; }
@font-face { font-family: KaTeX_Math; src: url("fonts/KaTeX_Math-BoldItalic.woff2") format("woff2"), url("fonts/KaTeX_Math-BoldItalic.woff") format("woff"), url("fonts/KaTeX_Math-BoldItalic.ttf") format("truetype"); font-weight: bold; font-style: italic; }
@font-face { font-family: KaTeX_Math; src: url("fonts/KaTeX_Math-Italic.woff2") format("woff2"), url("fonts/KaTeX_Math-Italic.woff") format("woff"), url("fonts/KaTeX_Math-Italic.ttf") format("truetype"); font-weight: normal; font-style: italic; }
@font-face { font-family: KaTeX_SansSerif; src: url("fonts/KaTeX_SansSerif-Bold.woff2") format("woff2"), url("fonts/KaTeX_SansSerif-Bold.woff") format("woff"), url("fonts/KaTeX_SansSerif-Bold.ttf") format("truetype"); font-weight: bold; font-style: normal; }
@font-face { font-family: KaTeX_SansSerif; src: url("fonts/KaTeX_SansSerif-Italic.woff2") format("woff2"), url("fonts/KaTeX_SansSerif-Italic.woff") format("woff"), url("fonts/KaTeX_SansSerif-Italic.ttf") format("truetype"); font-weight: normal; font-style: italic; }
@font-face { font-family: KaTeX_SansSerif; src: url("fonts/KaTeX_SansSerif-Regular.woff2") format("woff2"), url("fonts/KaTeX_SansSerif-Regular.woff") format("woff"), url("fonts/KaTeX_SansSerif-Regular.ttf") format("truetype"); font-weight: normal; font-style: normal; }
@font-face { font-family: KaTeX_Script; src: url("fonts/KaTeX_Script-Regular.woff2") format("woff2"), url("fonts/KaTeX_Script-Regular.woff") format("woff"), url("fonts/KaTeX_Script-Regular.ttf") format("truetype"); font-weight: normal; font-style: normal; }
@font-face { font-family: KaTeX_Size1; src: url("fonts/KaTeX_Size1-Regular.woff2") format("woff2"), url("fonts/KaTeX_Size1-Regular.woff") format("woff"), url("fonts/KaTeX_Size1-Regular.ttf") format("truetype"); font-weight: normal; font-style: normal; }
@font-face { font-family: KaTeX_Size2; src: url("fonts/KaTeX_Size2-Regular.woff2") format("woff2"), url("fonts/KaTeX_Size2-Regular.woff") format("woff"), url("fonts/KaTeX_Size2-Regular.ttf") format("truetype"); font-weight: normal; font-style: normal; }
@font-face { font-family: KaTeX_Size3; src: url("fonts/KaTeX_Size3-Regular.woff2") format("woff2"), url("fonts/KaTeX_Size3-Regular.woff") format("woff"), url("fonts/KaTeX_Size3-Regular.ttf") format("truetype"); font-weight: normal; font-style: normal; }
@font-face { font-family: KaTeX_Size4; src: url("fonts/KaTeX_Size4-Regular.woff2") format("woff2"), url("fonts/KaTeX_Size4-Regular.woff") format("woff"), url("fonts/KaTeX_Size4-Regular.ttf") format("truetype"); font-weight: normal; font-style: normal; }
@font-face { font-family: KaTeX_Typewriter; src: url("fonts/KaTeX_Typewriter-Regular.woff2") format("woff2"), url("fonts/KaTeX_Typewriter-Regular.woff") format("woff"), url("fonts/KaTeX_Typewriter-Regular.ttf") format("truetype"); font-weight: normal; font-style: normal; }
@media screen {
  .katex .mtable .vertical-separator { min-width: 1px; }
  .katex .mfrac .frac-line, .katex .overline .overline-line, .katex .underline .underline-line, .katex .hline, .katex .hdashline, .katex .rule { min-height: 1px; }
}
.katex-display { display: block; margin: 1em 0px; text-align: center; }
.katex-display > .katex { display: block; text-align: center; white-space: nowrap; }
.katex-display > .katex > .katex-html { display: block; }
.katex-display > .katex > .katex-html > .tag { position: absolute; right: 0px; }
.katex { font: 1.21em / 1.2 KaTeX_Main, "Times New Roman", serif; text-indent: 0px; text-rendering: auto; }
.katex * { forced-color-adjust: none !important; }
.katex .katex-mathml { position: absolute; clip: rect(1px, 1px, 1px, 1px); padding: 0px; border: 0px; height: 1px; width: 1px; overflow: hidden; }
.katex .katex-html { }
.katex .katex-html > .newline { display: block; }
.katex .base { position: relative; display: inline-block; white-space: nowrap; width: min-content; }
.katex .strut { display: inline-block; }
.katex .textbf { font-weight: bold; }
.katex .textit { font-style: italic; }
.katex .textrm { font-family: KaTeX_Main; }
.katex .textsf { font-family: KaTeX_SansSerif; }
.katex .texttt { font-family: KaTeX_Typewriter; }
.katex .mathit { font-family: KaTeX_Math; font-style: italic; }
.katex .mathrm { font-style: normal; }
.katex .mathbf { font-family: KaTeX_Main; font-weight: bold; }
.katex .boldsymbol { font-family: KaTeX_Math; font-weight: bold; font-style: italic; }
.katex .amsrm { font-family: KaTeX_AMS; }
.katex .mathbb, .katex .textbb { font-family: KaTeX_AMS; }
.katex .mathcal { font-family: KaTeX_Caligraphic; }
.katex .mathfrak, .katex .textfrak { font-family: KaTeX_Fraktur; }
.katex .mathtt { font-family: KaTeX_Typewriter; }
.katex .mathscr, .katex .textscr { font-family: KaTeX_Script; }
.katex .mathsf, .katex .textsf { font-family: KaTeX_SansSerif; }
.katex .mainit { font-family: KaTeX_Main; font-style: italic; }
.katex .mainrm { font-family: KaTeX_Main; font-style: normal; }
.katex .vlist-t { display: inline-table; table-layout: fixed; }
.katex .vlist-r { display: table-row; }
.katex .vlist { display: table-cell; vertical-align: bottom; position: relative; }
.katex .vlist > span { display: block; height: 0px; position: relative; }
.katex .vlist > span > span { display: inline-block; }
.katex .vlist > span > .pstrut { overflow: hidden; width: 0px; }
.katex .vlist-t2 { margin-right: -2px; }
.katex .vlist-s { display: table-cell; vertical-align: bottom; font-size: 1px; width: 2px; min-width: 2px; }
.katex .msupsub { text-align: left; }
.katex .mfrac > span > span { text-align: center; }
.katex .mfrac .frac-line { display: inline-block; width: 100%; border-bottom-style: solid; }
.katex .mspace { display: inline-block; }
.katex .llap, .katex .rlap, .katex .clap { width: 0px; position: relative; }
.katex .llap > .inner, .katex .rlap > .inner, .katex .clap > .inner { position: absolute; }
.katex .llap > .fix, .katex .rlap > .fix, .katex .clap > .fix { display: inline-block; }
.katex .llap > .inner { right: 0px; }
.katex .rlap > .inner, .katex .clap > .inner { left: 0px; }
.katex .clap > .inner > span { margin-left: -50%; margin-right: 50%; }
.katex .rule { display: inline-block; border: 0px solid; position: relative; }
.katex .overline .overline-line, .katex .underline .underline-line, .katex .hline { display: inline-block; width: 100%; border-bottom-style: solid; }
.katex .hdashline { display: inline-block; width: 100%; border-bottom-style: dashed; }
.katex .sqrt > .root { margin-left: 0.277778em; margin-right: -0.555556em; }
.katex .sizing, .katex .fontsize-ensurer { display: inline-block; }
.katex .sizing.reset-size1.size1, .katex .fontsize-ensurer.reset-size1.size1 { font-size: 1em; }
.katex .sizing.reset-size1.size2, .katex .fontsize-ensurer.reset-size1.size2 { font-size: 1.2em; }
.katex .sizing.reset-size1.size3, .katex .fontsize-ensurer.reset-size1.size3 { font-size: 1.4em; }
.katex .sizing.reset-size1.size4, .katex .fontsize-ensurer.reset-size1.size4 { font-size: 1.6em; }
.katex .sizing.reset-size1.size5, .katex .fontsize-ensurer.reset-size1.size5 { font-size: 1.8em; }
.katex .sizing.reset-size1.size6, .katex .fontsize-ensurer.reset-size1.size6 { font-size: 2em; }
.katex .sizing.reset-size1.size7, .katex .fontsize-ensurer.reset-size1.size7 { font-size: 2.4em; }
.katex .sizing.reset-size1.size8, .katex .fontsize-ensurer.reset-size1.size8 { font-size: 2.88em; }
.katex .sizing.reset-size1.size9, .katex .fontsize-ensurer.reset-size1.size9 { font-size: 3.456em; }
.katex .sizing.reset-size1.size10, .katex .fontsize-ensurer.reset-size1.size10 { font-size: 4.148em; }
.katex .sizing.reset-size1.size11, .katex .fontsize-ensurer.reset-size1.size11 { font-size: 4.976em; }
.katex .sizing.reset-size2.size1, .katex .fontsize-ensurer.reset-size2.size1 { font-size: 0.833333em; }
.katex .sizing.reset-size2.size2, .katex .fontsize-ensurer.reset-size2.size2 { font-size: 1em; }
.katex .sizing.reset-size2.size3, .katex .fontsize-ensurer.reset-size2.size3 { font-size: 1.16667em; }
.katex .sizing.reset-size2.size4, .katex .fontsize-ensurer.reset-size2.size4 { font-size: 1.33333em; }
.katex .sizing.reset-size2.size5, .katex .fontsize-ensurer.reset-size2.size5 { font-size: 1.5em; }
.katex .sizing.reset-size2.size6, .katex .fontsize-ensurer.reset-size2.size6 { font-size: 1.66667em; }
.katex .sizing.reset-size2.size7, .katex .fontsize-ensurer.reset-size2.size7 { font-size: 2em; }
.katex .sizing.reset-size2.size8, .katex .fontsize-ensurer.reset-size2.size8 { font-size: 2.4em; }
.katex .sizing.reset-size2.size9, .katex .fontsize-ensurer.reset-size2.size9 { font-size: 2.88em; }
.katex .sizing.reset-size2.size10, .katex .fontsize-ensurer.reset-size2.size10 { font-size: 3.45667em; }
.katex .sizing.reset-size2.size11, .katex .fontsize-ensurer.reset-size2.size11 { font-size: 4.14667em; }
.katex .sizing.reset-size3.size1, .katex .fontsize-ensurer.reset-size3.size1 { font-size: 0.714286em; }
.katex .sizing.reset-size3.size2, .katex .fontsize-ensurer.reset-size3.size2 { font-size: 0.857143em; }
.katex .sizing.reset-size3.size3, .katex .fontsize-ensurer.reset-size3.size3 { font-size: 1em; }
.katex .sizing.reset-size3.size4, .katex .fontsize-ensurer.reset-size3.size4 { font-size: 1.14286em; }
.katex .sizing.reset-size3.size5, .katex .fontsize-ensurer.reset-size3.size5 { font-size: 1.28571em; }
.katex .sizing.reset-size3.size6, .katex .fontsize-ensurer.reset-size3.size6 { font-size: 1.42857em; }
.katex .sizing.reset-size3.size7, .katex .fontsize-ensurer.reset-size3.size7 { font-size: 1.71429em; }
.katex .sizing.reset-size3.size8, .katex .fontsize-ensurer.reset-size3.size8 { font-size: 2.05714em; }
.katex .sizing.reset-size3.size9, .katex .fontsize-ensurer.reset-size3.size9 { font-size: 2.46857em; }
.katex .sizing.reset-size3.size10, .katex .fontsize-ensurer.reset-size3.size10 { font-size: 2.96286em; }
.katex .sizing.reset-size3.size11, .katex .fontsize-ensurer.reset-size3.size11 { font-size: 3.55429em; }
.katex .sizing.reset-size4.size1, .katex .fontsize-ensurer.reset-size4.size1 { font-size: 0.625em; }
.katex .sizing.reset-size4.size2, .katex .fontsize-ensurer.reset-size4.size2 { font-size: 0.75em; }
.katex .sizing.reset-size4.size3, .katex .fontsize-ensurer.reset-size4.size3 { font-size: 0.875em; }
.katex .sizing.reset-size4.size4, .katex .fontsize-ensurer.reset-size4.size4 { font-size: 1em; }
.katex .sizing.reset-size4.size5, .katex .fontsize-ensurer.reset-size4.size5 { font-size: 1.125em; }
.katex .sizing.reset-size4.size6, .katex .fontsize-ensurer.reset-size4.size6 { font-size: 1.25em; }
.katex .sizing.reset-size4.size7, .katex .fontsize-ensurer.reset-size4.size7 { font-size: 1.5em; }
.katex .sizing.reset-size4.size8, .katex .fontsize-ensurer.reset-size4.size8 { font-size: 1.8em; }
.katex .sizing.reset-size4.size9, .katex .fontsize-ensurer.reset-size4.size9 { font-size: 2.16em; }
.katex .sizing.reset-size4.size10, .katex .fontsize-ensurer.reset-size4.size10 { font-size: 2.5925em; }
.katex .sizing.reset-size4.size11, .katex .fontsize-ensurer.reset-size4.size11 { font-size: 3.11em; }
.katex .sizing.reset-size5.size1, .katex .fontsize-ensurer.reset-size5.size1 { font-size: 0.555556em; }
.katex .sizing.reset-size5.size2, .katex .fontsize-ensurer.reset-size5.size2 { font-size: 0.666667em; }
.katex .sizing.reset-size5.size3, .katex .fontsize-ensurer.reset-size5.size3 { font-size: 0.777778em; }
.katex .sizing.reset-size5.size4, .katex .fontsize-ensurer.reset-size5.size4 { font-size: 0.888889em; }
.katex .sizing.reset-size5.size5, .katex .fontsize-ensurer.reset-size5.size5 { font-size: 1em; }
.katex .sizing.reset-size5.size6, .katex .fontsize-ensurer.reset-size5.size6 { font-size: 1.11111em; }
.katex .sizing.reset-size5.size7, .katex .fontsize-ensurer.reset-size5.size7 { font-size: 1.33333em; }
.katex .sizing.reset-size5.size8, .katex .fontsize-ensurer.reset-size5.size8 { font-size: 1.6em; }
.katex .sizing.reset-size5.size9, .katex .fontsize-ensurer.reset-size5.size9 { font-size: 1.92em; }
.katex .sizing.reset-size5.size10, .katex .fontsize-ensurer.reset-size5.size10 { font-size: 2.30444em; }
.katex .sizing.reset-size5.size11, .katex .fontsize-ensurer.reset-size5.size11 { font-size: 2.76444em; }
.katex .sizing.reset-size6.size1, .katex .fontsize-ensurer.reset-size6.size1 { font-size: 0.5em; }
.katex .sizing.reset-size6.size2, .katex .fontsize-ensurer.reset-size6.size2 { font-size: 0.6em; }
.katex .sizing.reset-size6.size3, .katex .fontsize-ensurer.reset-size6.size3 { font-size: 0.7em; }
.katex .sizing.reset-size6.size4, .katex .fontsize-ensurer.reset-size6.size4 { font-size: 0.8em; }
.katex .sizing.reset-size6.size5, .katex .fontsize-ensurer.reset-size6.size5 { font-size: 0.9em; }
.katex .sizing.reset-size6.size6, .katex .fontsize-ensurer.reset-size6.size6 { font-size: 1em; }
.katex .sizing.reset-size6.size7, .katex .fontsize-ensurer.reset-size6.size7 { font-size: 1.2em; }
.katex .sizing.reset-size6.size8, .katex .fontsize-ensurer.reset-size6.size8 { font-size: 1.44em; }
.katex .sizing.reset-size6.size9, .katex .fontsize-ensurer.reset-size6.size9 { font-size: 1.728em; }
.katex .sizing.reset-size6.size10, .katex .fontsize-ensurer.reset-size6.size10 { font-size: 2.074em; }
.katex .sizing.reset-size6.size11, .katex .fontsize-ensurer.reset-size6.size11 { font-size: 2.488em; }
.katex .sizing.reset-size7.size1, .katex .fontsize-ensurer.reset-size7.size1 { font-size: 0.416667em; }
.katex .sizing.reset-size7.size2, .katex .fontsize-ensurer.reset-size7.size2 { font-size: 0.5em; }
.katex .sizing.reset-size7.size3, .katex .fontsize-ensurer.reset-size7.size3 { font-size: 0.583333em; }
.katex .sizing.reset-size7.size4, .katex .fontsize-ensurer.reset-size7.size4 { font-size: 0.666667em; }
.katex .sizing.reset-size7.size5, .katex .fontsize-ensurer.reset-size7.size5 { font-size: 0.75em; }
.katex .sizing.reset-size7.size6, .katex .fontsize-ensurer.reset-size7.size6 { font-size: 0.833333em; }
.katex .sizing.reset-size7.size7, .katex .fontsize-ensurer.reset-size7.size7 { font-size: 1em; }
.katex .sizing.reset-size7.size8, .katex .fontsize-ensurer.reset-size7.size8 { font-size: 1.2em; }
.katex .sizing.reset-size7.size9, .katex .fontsize-ensurer.reset-size7.size9 { font-size: 1.44em; }
.katex .sizing.reset-size7.size10, .katex .fontsize-ensurer.reset-size7.size10 { font-size: 1.72833em; }
.katex .sizing.reset-size7.size11, .katex .fontsize-ensurer.reset-size7.size11 { font-size: 2.07333em; }
.katex .sizing.reset-size8.size1, .katex .fontsize-ensurer.reset-size8.size1 { font-size: 0.347222em; }
.katex .sizing.reset-size8.size2, .katex .fontsize-ensurer.reset-size8.size2 { font-size: 0.416667em; }
.katex .sizing.reset-size8.size3, .katex .fontsize-ensurer.reset-size8.size3 { font-size: 0.486111em; }
.katex .sizing.reset-size8.size4, .katex .fontsize-ensurer.reset-size8.size4 { font-size: 0.555556em; }
.katex .sizing.reset-size8.size5, .katex .fontsize-ensurer.reset-size8.size5 { font-size: 0.625em; }
.katex .sizing.reset-size8.size6, .katex .fontsize-ensurer.reset-size8.size6 { font-size: 0.694444em; }
.katex .sizing.reset-size8.size7, .katex .fontsize-ensurer.reset-size8.size7 { font-size: 0.833333em; }
.katex .sizing.reset-size8.size8, .katex .fontsize-ensurer.reset-size8.size8 { font-size: 1em; }
.katex .sizing.reset-size8.size9, .katex .fontsize-ensurer.reset-size8.size9 { font-size: 1.2em; }
.katex .sizing.reset-size8.size10, .katex .fontsize-ensurer.reset-size8.size10 { font-size: 1.44028em; }
.katex .sizing.reset-size8.size11, .katex .fontsize-ensurer.reset-size8.size11 { font-size: 1.72778em; }
.katex .sizing.reset-size9.size1, .katex .fontsize-ensurer.reset-size9.size1 { font-size: 0.289352em; }
.katex .sizing.reset-size9.size2, .katex .fontsize-ensurer.reset-size9.size2 { font-size: 0.347222em; }
.katex .sizing.reset-size9.size3, .katex .fontsize-ensurer.reset-size9.size3 { font-size: 0.405093em; }
.katex .sizing.reset-size9.size4, .katex .fontsize-ensurer.reset-size9.size4 { font-size: 0.462963em; }
.katex .sizing.reset-size9.size5, .katex .fontsize-ensurer.reset-size9.size5 { font-size: 0.520833em; }
.katex .sizing.reset-size9.size6, .katex .fontsize-ensurer.reset-size9.size6 { font-size: 0.578704em; }
.katex .sizing.reset-size9.size7, .katex .fontsize-ensurer.reset-size9.size7 { font-size: 0.694444em; }
.katex .sizing.reset-size9.size8, .katex .fontsize-ensurer.reset-size9.size8 { font-size: 0.833333em; }
.katex .sizing.reset-size9.size9, .katex .fontsize-ensurer.reset-size9.size9 { font-size: 1em; }
.katex .sizing.reset-size9.size10, .katex .fontsize-ensurer.reset-size9.size10 { font-size: 1.20023em; }
.katex .sizing.reset-size9.size11, .katex .fontsize-ensurer.reset-size9.size11 { font-size: 1.43981em; }
.katex .sizing.reset-size10.size1, .katex .fontsize-ensurer.reset-size10.size1 { font-size: 0.24108em; }
.katex .sizing.reset-size10.size2, .katex .fontsize-ensurer.reset-size10.size2 { font-size: 0.289296em; }
.katex .sizing.reset-size10.size3, .katex .fontsize-ensurer.reset-size10.size3 { font-size: 0.337512em; }
.katex .sizing.reset-size10.size4, .katex .fontsize-ensurer.reset-size10.size4 { font-size: 0.385728em; }
.katex .sizing.reset-size10.size5, .katex .fontsize-ensurer.reset-size10.size5 { font-size: 0.433944em; }
.katex .sizing.reset-size10.size6, .katex .fontsize-ensurer.reset-size10.size6 { font-size: 0.48216em; }
.katex .sizing.reset-size10.size7, .katex .fontsize-ensurer.reset-size10.size7 { font-size: 0.578592em; }
.katex .sizing.reset-size10.size8, .katex .fontsize-ensurer.reset-size10.size8 { font-size: 0.694311em; }
.katex .sizing.reset-size10.size9, .katex .fontsize-ensurer.reset-size10.size9 { font-size: 0.833173em; }
.katex .sizing.reset-size10.size10, .katex .fontsize-ensurer.reset-size10.size10 { font-size: 1em; }
.katex .sizing.reset-size10.size11, .katex .fontsize-ensurer.reset-size10.size11 { font-size: 1.19961em; }
.katex .sizing.reset-size11.size1, .katex .fontsize-ensurer.reset-size11.size1 { font-size: 0.200965em; }
.katex .sizing.reset-size11.size2, .katex .fontsize-ensurer.reset-size11.size2 { font-size: 0.241158em; }
.katex .sizing.reset-size11.size3, .katex .fontsize-ensurer.reset-size11.size3 { font-size: 0.28135em; }
.katex .sizing.reset-size11.size4, .katex .fontsize-ensurer.reset-size11.size4 { font-size: 0.321543em; }
.katex .sizing.reset-size11.size5, .katex .fontsize-ensurer.reset-size11.size5 { font-size: 0.361736em; }
.katex .sizing.reset-size11.size6, .katex .fontsize-ensurer.reset-size11.size6 { font-size: 0.401929em; }
.katex .sizing.reset-size11.size7, .katex .fontsize-ensurer.reset-size11.size7 { font-size: 0.482315em; }
.katex .sizing.reset-size11.size8, .katex .fontsize-ensurer.reset-size11.size8 { font-size: 0.578778em; }
.katex .sizing.reset-size11.size9, .katex .fontsize-ensurer.reset-size11.size9 { font-size: 0.694534em; }
.katex .sizing.reset-size11.size10, .katex .fontsize-ensurer.reset-size11.size10 { font-size: 0.833601em; }
.katex .sizing.reset-size11.size11, .katex .fontsize-ensurer.reset-size11.size11 { font-size: 1em; }
.katex .delimsizing.size1 { font-family: KaTeX_Size1; }
.katex .delimsizing.size2 { font-family: KaTeX_Size2; }
.katex .delimsizing.size3 { font-family: KaTeX_Size3; }
.katex .delimsizing.size4 { font-family: KaTeX_Size4; }
.katex .delimsizing.mult .delim-size1 > span { font-family: KaTeX_Size1; }
.katex .delimsizing.mult .delim-size4 > span { font-family: KaTeX_Size4; }
.katex .nulldelimiter { display: inline-block; width: 0.12em; }
.katex .delimcenter { position: relative; }
.katex .op-symbol { position: relative; }
.katex .op-symbol.small-op { font-family: KaTeX_Size1; }
.katex .op-symbol.large-op { font-family: KaTeX_Size2; }
.katex .op-limits > .vlist-t { text-align: center; }
.katex .accent > .vlist-t { text-align: center; }
.katex .accent .accent-body:not(.accent-full) { width: 0px; }
.katex .accent .accent-body { position: relative; }
.katex .overlay { display: block; }
.katex .mtable .vertical-separator { display: inline-block; margin: 0px -0.025em; border-right: 0.05em solid; }
.katex .mtable .vs-dashed { border-right: 0.05em dashed; }
.katex .mtable .arraycolsep { display: inline-block; }
.katex .mtable .col-align-c > .vlist-t { text-align: center; }
.katex .mtable .col-align-l > .vlist-t { text-align: left; }
.katex .mtable .col-align-r > .vlist-t { text-align: right; }
.katex .svg-align { text-align: left; }
.katex svg, .screenShotTempCanvas { display: block; position: absolute; width: 100%; height: inherit; fill: currentcolor; stroke: currentcolor; fill-rule: nonzero; fill-opacity: 1; stroke-width: 1; stroke-linecap: butt; stroke-linejoin: miter; stroke-miterlimit: 4; stroke-dasharray: none; stroke-dashoffset: 0; stroke-opacity: 1; }
.katex svg path { stroke: none; }
.katex .stretchy { width: 100%; display: block; position: relative; overflow: hidden; }
.katex .stretchy::before, .katex .stretchy::after { content: ""; }
.katex .hide-tail { width: 100%; position: relative; overflow: hidden; }
.katex .halfarrow-left { position: absolute; left: 0px; width: 50.2%; overflow: hidden; }
.katex .halfarrow-right { position: absolute; right: 0px; width: 50.2%; overflow: hidden; }
.katex .brace-left { position: absolute; left: 0px; width: 25.1%; overflow: hidden; }
.katex .brace-center { position: absolute; left: 25%; width: 50%; overflow: hidden; }
.katex .brace-right { position: absolute; right: 0px; width: 25.1%; overflow: hidden; }
.katex .x-arrow-pad { padding: 0px 0.5em; }
.katex .x-arrow, .katex .mover, .katex .munder { text-align: center; }
.katex .boxpad { padding: 0px 0.3em; }
.katex .fbox { box-sizing: border-box; border: 0.04em solid black; }
.katex .fcolorbox { box-sizing: border-box; border: 0.04em solid; }
.katex .cancel-pad { padding: 0px 0.2em; }
.katex .cancel-lap { margin-left: -0.2em; margin-right: -0.2em; }
.katex .sout { border-bottom-style: solid; border-bottom-width: 0.08em; }
.output_wrapper pre code { display: -webkit-box !important; } 
.output_wrapper .hljs{display: block; overflow-x: auto; padding: 0.5em; color: rgb(56, 58, 66); background: rgb(250, 250, 250);}

.output_wrapper .hljs-comment,.output_wrapper  .hljs-quote{color: rgb(160, 161, 167); font-style: italic;}

.output_wrapper .hljs-doctag,.output_wrapper  .hljs-keyword,.output_wrapper  .hljs-formula{color: rgb(166, 38, 164);}

.output_wrapper .hljs-section,.output_wrapper  .hljs-name,.output_wrapper  .hljs-selector-tag,.output_wrapper  .hljs-deletion,.output_wrapper  .hljs-subst{color: rgb(228, 86, 73);}

.output_wrapper .hljs-literal{color: rgb(1, 132, 187);}

.output_wrapper .hljs-string,.output_wrapper  .hljs-regexp,.output_wrapper  .hljs-addition,.output_wrapper  .hljs-attribute,.output_wrapper  .hljs-meta-string{color: rgb(80, 161, 79);}

.output_wrapper .hljs-built_in,.output_wrapper  .hljs-class .hljs-title{color: rgb(193, 132, 1);}

.output_wrapper .hljs-attr,.output_wrapper  .hljs-variable,.output_wrapper  .hljs-template-variable,.output_wrapper  .hljs-type,.output_wrapper  .hljs-selector-class,.output_wrapper  .hljs-selector-attr,.output_wrapper  .hljs-selector-pseudo,.output_wrapper  .hljs-number{color: rgb(152, 104, 1);}

.output_wrapper .hljs-symbol,.output_wrapper  .hljs-bullet,.output_wrapper  .hljs-link,.output_wrapper  .hljs-meta,.output_wrapper  .hljs-selector-id,.output_wrapper  .hljs-title{color: rgb(64, 120, 242);}

.output_wrapper .hljs-emphasis{font-style: italic;}

.output_wrapper .hljs-strong{font-weight: bold;}

.output_wrapper .hljs-link{text-decoration: underline;}
 
.output_wrapper pre code {line-height: 18px; font-size: 14px; font-weight: normal; word-spacing: 0px; letter-spacing: 0px;} 
.output_wrapper{font-size: 15px; color: rgb(62, 62, 62); line-height: 1.8; word-spacing: 2px; letter-spacing: 2px; font-family: "Helvetica Neue", Helvetica, "Hiragino Sans GB", "Microsoft YaHei", Arial, sans-serif; background-image: linear-gradient(90deg, rgba(50, 0, 0, 0.05) 3%, rgba(0, 0, 0, 0) 3%), linear-gradient(360deg, rgba(50, 0, 0, 0.05) 3%, rgba(0, 0, 0, 0) 3%); background-size: 20px 20px; background-position: center center;}

.output_wrapper *{font-size: inherit; color: inherit; line-height: inherit; margin: 0px; padding: 0px;}

.output_wrapper p{margin: 1.7em 0px;}

.output_wrapper h1,.output_wrapper  h2,.output_wrapper  h3,.output_wrapper  h4,.output_wrapper  h5,.output_wrapper  h6{margin: 1.6em 0px; font-weight: bold;}

.output_wrapper h1{font-size: 1.6em;}

.output_wrapper h2{font-size: 1.4em;}

.output_wrapper h3{font-size: 1.3em;}

.output_wrapper h4{font-size: 1.2em;}

.output_wrapper h5{font-size: 1em;}

.output_wrapper h6{font-size: 1em;}

.output_wrapper h3{border-bottom: 2px solid rgb(239, 112, 96); font-size: 1.3em;}

.output_wrapper h3 span{display: inline-block; font-weight: normal; background: rgb(239, 112, 96); color: rgb(255, 255, 255); padding: 3px 10px 1px; border-top-right-radius: 3px; border-top-left-radius: 3px; margin-right: 3px;}

.output_wrapper h3::after{display: inline-block; content: " "; vertical-align: bottom; border-bottom: 36px solid rgb(239, 235, 233); border-right: 20px solid transparent;}

.output_wrapper ul,.output_wrapper  ol{padding-left: 32px;}

.output_wrapper ul{list-style-type: disc;}

.output_wrapper ol{list-style-type: decimal;}

.output_wrapper li *{}

.output_wrapper li{margin-bottom: 0.5em;}

.output_wrapper .code_size_default{line-height: 18px; font-size: 14px; font-weight: normal; word-spacing: 0px; letter-spacing: 0px;}

.output_wrapper .code_size_tight{line-height: 15px; font-size: 11px; font-weight: normal; word-spacing: -3px; letter-spacing: 0px;}

.output_wrapper pre code{font-family: Consolas, Inconsolata, Courier, monospace; border-radius: 0px;}

.output_wrapper blockquote{display: block; padding: 15px 15px 15px 1rem; font-size: 0.9em; margin: 1em 0px; color: rgb(0, 0, 0); border-left: 5px solid rgb(239, 112, 96); background: rgb(239, 235, 233); overflow: auto; overflow-wrap: normal; word-break: normal;}

.output_wrapper blockquote p{margin: 0px;}

.output_wrapper a{text-decoration: none; color: rgb(30, 107, 184); overflow-wrap: break-word;}

.output_wrapper strong{font-weight: bold; color: rgb(233, 105, 0);}

.output_wrapper em{color: rgb(98, 0, 234);}

.output_wrapper del{font-style: italic; text-decoration: none; color: rgb(41, 98, 255);}

.output_wrapper strong em{font-weight: bold; color: rgb(197, 17, 98);}

.output_wrapper hr{height: 1px; margin: 1.5rem 0px; border-right: none; border-bottom: none; border-left: none; border-image: initial; border-top: 1px dashed rgb(165, 165, 165);}

.output_wrapper code{overflow-wrap: break-word; padding: 2px 4px; border-radius: 4px; margin: 0px 2px; color: rgb(248, 35, 117); background: rgb(248, 248, 248);}

.output_wrapper img{display: block; margin: 0px auto; max-width: 100%;}

.output_wrapper figcaption{margin-top: 10px; text-align: center; color: rgb(153, 153, 153); font-size: 0.7em;}

.output_wrapper table{display: table; width: 100%; text-align: left;}

.output_wrapper tbody{border: 0px;}

.output_wrapper table tr{border-width: 1px 0px 0px; border-right-style: initial; border-bottom-style: initial; border-left-style: initial; border-right-color: initial; border-bottom-color: initial; border-left-color: initial; border-image: initial; border-top-style: solid; border-top-color: rgb(204, 204, 204); background-color: white;}

.output_wrapper table tr:nth-child(2n){background-color: rgb(248, 248, 248);}

.output_wrapper table tr th,.output_wrapper  table tr td{font-size: 1em; border: 1px solid rgb(204, 204, 204); padding: 0.5em 1em; text-align: left;}

.output_wrapper table tr th{font-weight: bold; background-color: rgb(240, 240, 240);}

.output_wrapper .katex-display{font-size: 1.22em;}

.output_wrapper .katex{padding: 8px 3px;}

.output_wrapper .katex-display > .katex{display: inline-block; text-align: center; padding: 3px;}

.output_wrapper .katex img{display: inline-block; vertical-align: middle;}

.output_wrapper a[href^="#"] sup{vertical-align: super; margin: 0px 2px; padding: 1px 3px; color: rgb(255, 255, 255); background: rgb(102, 102, 102); font-size: 0.7em;}

.output_wrapper .task-list-list{list-style-type: none;}

.output_wrapper .task-list-list.checked{color: rgb(62, 62, 62);}

.output_wrapper .task-list-list.uncheck{color: rgb(191, 193, 191);}

.output_wrapper .task-list-list .icon_uncheck,.output_wrapper  .task-list-list .icon_check{display: inline-block; vertical-align: middle; margin-right: 10px;}

.output_wrapper .task-list-list .icon_check::before{content: "√"; border: 2px solid rgb(62, 62, 62); color: red;}

.output_wrapper .task-list-list .icon_uncheck::before{content: "x"; border: 2px solid rgb(191, 193, 191); color: rgb(191, 193, 191);}

.output_wrapper .task-list-list .icon_check::before,.output_wrapper  .task-list-list .icon_uncheck::before{padding: 2px 8px 2px 5px; border-radius: 5px;}

.output_wrapper .toc{margin-left: 25px;}

.output_wrapper .toc_item{display: block;}

.output_wrapper .toc_left{margin-left: 25px;}
 
</style>  
  <style type="text/css" id="export_setting_css">body { width: 100%; margin: 0px; padding: 0px; background: rgb(81, 154, 178); }
#export_content { margin: 40px 20%; padding: 20px; border: 1px solid rgb(149, 155, 111); background: rgb(255, 255, 255); }</style>  

</head><body><div id="export_content"><div class="output_wrapper" id="output_wrapper_id"><h1 id="h"><span>动态规划</span></h1>
<p>本文先通过一道题的求解过程逐步带大家了解动态规划，后续会做一些练习，带大家解决动态规划相关题目</p>
<h3 id="h1offer10ihttpsleetcodecncomproblemsfeibonaqishulielcof"><span>1. 首先看一道算法题 —— <a href="https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof/">剑指 Offer 10- I. 斐波那契数列</a></span></h3>
<p>写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项。斐波那契数列的定义如下：</p>
<pre><code class="hljs r"><span class="linenum hljs-number">1</span><span class="hljs-literal">F</span>(<span class="hljs-number">0</span>)&nbsp;=&nbsp;<span class="hljs-number">0</span>,&nbsp;&nbsp;&nbsp;<span class="hljs-literal">F</span>(<span class="hljs-number">1</span>)&nbsp;=&nbsp;<span class="hljs-number">1</span><br><span class="linenum hljs-number">2</span><span class="hljs-literal">F</span>(N)&nbsp;=&nbsp;<span class="hljs-literal">F</span>(N&nbsp;-&nbsp;<span class="hljs-number">1</span>)&nbsp;+&nbsp;<span class="hljs-literal">F</span>(N&nbsp;-&nbsp;<span class="hljs-number">2</span>),&nbsp;其中&nbsp;N&nbsp;&gt;&nbsp;<span class="hljs-number">1.</span><br></code></pre>
<p>斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。</p>
<p>答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1</p>
<h4 id="h11"><span>1.1. 首先我们想到的可能是递归</span></h4>
<pre><code class="java language-java hljs"><span class="linenum hljs-number">1</span><span class="hljs-function"><span class="hljs-keyword">public</span>&nbsp;<span class="hljs-keyword">int</span>&nbsp;<span class="hljs-title">fib</span><span class="hljs-params">(<span class="hljs-keyword">int</span>&nbsp;n)</span>&nbsp;</span>{<br><span class="linenum hljs-number">2</span><br><span class="linenum hljs-number">3</span>&nbsp;&nbsp;&nbsp;&nbsp;<span class="hljs-keyword">if</span>&nbsp;(n&nbsp;==&nbsp;<span class="hljs-number">0</span>)&nbsp;<span class="hljs-keyword">return</span>&nbsp;<span class="hljs-number">0</span>;<br><span class="linenum hljs-number">4</span>&nbsp;&nbsp;&nbsp;&nbsp;<span class="hljs-keyword">if</span>&nbsp;(n&nbsp;==&nbsp;<span class="hljs-number">1</span>)&nbsp;<span class="hljs-keyword">return</span>&nbsp;<span class="hljs-number">1</span>;<br><span class="linenum hljs-number">5</span><br><span class="linenum hljs-number">6</span>&nbsp;&nbsp;&nbsp;&nbsp;<span class="hljs-keyword">return</span>&nbsp;(fib(n&nbsp;-&nbsp;<span class="hljs-number">1</span>)&nbsp;+&nbsp;fib(n&nbsp;-&nbsp;<span class="hljs-number">2</span>))&nbsp;%&nbsp;<span class="hljs-number">1000000007</span>;<br><span class="linenum hljs-number">7</span>}<br></code></pre>
<p><img src="https://p3-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/841961d86fef4d389d760ae5ad1cdcfc~tplv-k3u1fbpfcp-watermark.image" style="zoom:150%;"></p>
<p>原理：通过把f(n) 分解成 f(n - 1) 和 f(n - 2) 两个子问题计算，并递归，直到终止条件为止</p>
<p>缺点：通过上图可以看出递归会有大量的重复调用过程，时间利用率是O(2^n)</p>
<h4 id="h12"><span>1.2. 记忆化搜索/备忘录算法</span></h4>
<pre><code class="java language-java hljs"><span class="linenum hljs-number"> 1</span>Map&lt;Integer,&nbsp;Integer&gt;&nbsp;memo&nbsp;=&nbsp;<span class="hljs-keyword">new</span>&nbsp;HashMap&lt;&gt;();<br><span class="linenum hljs-number"> 2</span><br><span class="linenum hljs-number"> 3</span><span class="hljs-function"><span class="hljs-keyword">public</span>&nbsp;<span class="hljs-keyword">int</span>&nbsp;<span class="hljs-title">fib</span><span class="hljs-params">(<span class="hljs-keyword">int</span>&nbsp;n)</span>&nbsp;</span>{<br><span class="linenum hljs-number"> 4</span><br><span class="linenum hljs-number"> 5</span>&nbsp;&nbsp;&nbsp;&nbsp;<span class="hljs-keyword">if</span>&nbsp;(n&nbsp;==&nbsp;<span class="hljs-number">0</span>)&nbsp;<span class="hljs-keyword">return</span>&nbsp;<span class="hljs-number">0</span>;<br><span class="linenum hljs-number"> 6</span>&nbsp;&nbsp;&nbsp;&nbsp;<span class="hljs-keyword">if</span>&nbsp;(n&nbsp;==&nbsp;<span class="hljs-number">1</span>)&nbsp;<span class="hljs-keyword">return</span>&nbsp;<span class="hljs-number">1</span>;<br><span class="linenum hljs-number"> 7</span>&nbsp;&nbsp;&nbsp;&nbsp;<span class="hljs-keyword">if</span>&nbsp;(!memo.containsKey(n))<br><span class="linenum hljs-number"> 8</span>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;memo.put(n,&nbsp;fib(n&nbsp;-&nbsp;<span class="hljs-number">1</span>)&nbsp;+&nbsp;fib(n&nbsp;-&nbsp;<span class="hljs-number">2</span>));<br><span class="linenum hljs-number"> 9</span><br><span class="linenum hljs-number">10</span>&nbsp;&nbsp;&nbsp;&nbsp;<span class="hljs-keyword">return</span>&nbsp;memo.get(n);<br><span class="linenum hljs-number">11</span>}<br></code></pre>
<p>这种方法是把计算结果保存起来（剪枝），下次可以直接拿来用，这种方法也是有缺点的：需要额外O(n)的空间</p>
<blockquote>
  <p>记忆化搜索是自上而下解决问题，如果一个问题可以自上而下解决，那么它也可以自下而上解决——动态规划DP</p>
</blockquote>
<p>上面的方法改为自下而上实现</p>
<pre><code class="java language-java hljs"><span class="linenum hljs-number"> 1</span><span class="hljs-function"><span class="hljs-keyword">public</span>&nbsp;<span class="hljs-keyword">int</span>&nbsp;<span class="hljs-title">fib</span><span class="hljs-params">(<span class="hljs-keyword">int</span>&nbsp;n)</span>&nbsp;</span>{<br><span class="linenum hljs-number"> 2</span>&nbsp;&nbsp;&nbsp;&nbsp;Map&lt;Integer,&nbsp;Integer&gt;&nbsp;memo&nbsp;=&nbsp;<span class="hljs-keyword">new</span>&nbsp;HashMap&lt;&gt;();<br><span class="linenum hljs-number"> 3</span>&nbsp;&nbsp;&nbsp;&nbsp;memo.put(<span class="hljs-number">0</span>,&nbsp;<span class="hljs-number">0</span>);<br><span class="linenum hljs-number"> 4</span>&nbsp;&nbsp;&nbsp;&nbsp;memo.put(<span class="hljs-number">1</span>,&nbsp;<span class="hljs-number">1</span>);<br><span class="linenum hljs-number"> 5</span><br><span class="linenum hljs-number"> 6</span>&nbsp;&nbsp;&nbsp;&nbsp;<span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span>&nbsp;i&nbsp;=&nbsp;<span class="hljs-number">2</span>;&nbsp;i&nbsp;&lt;=&nbsp;n;&nbsp;i&nbsp;++)&nbsp;{<br><span class="linenum hljs-number"> 7</span>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;memo.put(i,&nbsp;memo.get(i&nbsp;-&nbsp;<span class="hljs-number">1</span>),&nbsp;memo.get(i&nbsp;-&nbsp;<span class="hljs-number">2</span>));<br><span class="linenum hljs-number"> 8</span>&nbsp;&nbsp;&nbsp;&nbsp;}<br><span class="linenum hljs-number"> 9</span>&nbsp;&nbsp;&nbsp;&nbsp;<span class="hljs-keyword">return</span>&nbsp;memo.get(n);<br><span class="linenum hljs-number">10</span>}<br></code></pre>
<p>记忆化搜索时间复杂度已经优化的很好了，但是需要额外的空间，有什么方法可以不用额外申请空间呢？接下来我们看下动态规划(DP) </p>
<h4 id="h13dp"><span>1.3. 使用动态规划(DP)解答上面的问题</span></h4>
<p>其实自下而上的记忆化方法已经算是DP了，只是用到了额外的map空间，我们把它修改下，用两个指针记录子问题的解</p>
<pre><code class="java language-java hljs"><span class="linenum hljs-number"> 1</span><span class="hljs-function"><span class="hljs-keyword">public</span>&nbsp;<span class="hljs-keyword">int</span>&nbsp;<span class="hljs-title">fibDp</span><span class="hljs-params">(<span class="hljs-keyword">int</span>&nbsp;n)</span>&nbsp;</span>{<br><span class="linenum hljs-number"> 2</span>&nbsp;&nbsp;&nbsp;&nbsp;<span class="hljs-keyword">int</span>&nbsp;pre&nbsp;=&nbsp;<span class="hljs-number">0</span>,&nbsp;cur&nbsp;=&nbsp;<span class="hljs-number">1</span>,&nbsp;sum;<br><span class="linenum hljs-number"> 3</span><br><span class="linenum hljs-number"> 4</span>&nbsp;&nbsp;&nbsp;&nbsp;<span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span>&nbsp;i&nbsp;=&nbsp;<span class="hljs-number">0</span>;&nbsp;i&nbsp;&lt;&nbsp;n;&nbsp;i&nbsp;++)&nbsp;{<br><span class="linenum hljs-number"> 5</span>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;sum&nbsp;=&nbsp;(pre&nbsp;+&nbsp;cur)&nbsp;%&nbsp;<span class="hljs-number">1000000007</span>;<br><span class="linenum hljs-number"> 6</span>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;pre&nbsp;=&nbsp;cur;<br><span class="linenum hljs-number"> 7</span>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;cur&nbsp;=&nbsp;sum;<br><span class="linenum hljs-number"> 8</span>&nbsp;&nbsp;&nbsp;&nbsp;}<br><span class="linenum hljs-number"> 9</span><br><span class="linenum hljs-number">10</span>&nbsp;&nbsp;&nbsp;&nbsp;<span class="hljs-keyword">return</span>&nbsp;cur;<br><span class="linenum hljs-number">11</span>}<br></code></pre>
<h3 id="h2dynamicprogramming"><span>2. 动态规划 (Dynamic Programming)</span></h3>
<p><strong>首先看下动态规划的定义：</strong></p>
<p>将原问题拆解成若干子问题，同时保存子问题的答案，使得每个子问题只求解一次，最终获得原问题的答案</p>
<p>动态规划算法的基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解</p>
<p><strong>那么我们什么时候可以用到动态规划呢</strong></p>
<p>根据定义我们可以得出：当一个大的问题可以拆分成多个结构相同的子问题，且子问题的解可以被多次使用，这时我们就可以用DP来解决</p>
<p><strong>动态规划的一般解题思路：</strong></p>
<ul>
<li><span>最优子结构：首先需要定义子结构，也就是拆分成的子问题结构</span></li>
<li><span>边界：然后我们需要找到问题的边界，相当于递归的出点</span></li>
<li><span>状态转移公式：最后把子问题通过转移方程递推得到最终答案</span></li>
</ul>
<h3 id="h3"><span>3.  相似问题：</span></h3>
<h4 id="h31offer10iihttpsleetcodecncomproblemsqingwatiaotaijiewentilcof"><span>3.1 <a href="https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/">剑指 Offer 10- II. 青蛙跳台阶问题</a></span></h4>
<p>和斐波那契额数列类似，忽略</p>
<h4 id="h32198httpsleetcodecncomproblemshouserobber"><span>3.2 <a href="https://leetcode-cn.com/problems/house-robber/">198. 打家劫舍</a></span></h4>
<p>你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。</p>
<p>给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。 </p>
<p>示例 1：</p>
<p>输入：[1,2,3,1]<br>输出：4<br>解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。<br>     偷窃到的最高金额 = 1 + 3 = 4 。<br>示例 2：</p>
<p>输入：[2,7,9,3,1]<br>输出：12<br>解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。<br>     偷窃到的最高金额 = 2 + 9 + 1 = 12 。</p>
<p><strong>分析</strong></p>
<p>如果房屋数量大于两间，应该如何计算能够偷窃到的最高总金额呢？对于第 k~(k&gt;2)k (k&gt;2) 间房屋，有两个选项：</p>
<ul>
<li><span>偷窃第 kk 间房屋，那么就不能偷窃第 k-1k−1 间房屋，偷窃总金额为前 k-2k−2 间房屋的最高总金额与第 kk 间房屋的金额之和</span></li>
<li><span>不偷窃第 kk 间房屋，偷窃总金额为前 k-1k−1 间房屋的最高总金额</span></li>
</ul>
<p>转移方程为：</p>
<pre><code class="java language-java hljs"><span class="linenum hljs-number">1</span>dp[i]=max(dp[i−<span class="hljs-number">2</span>]+nums[i],dp[i−<span class="hljs-number">1</span>])<br></code></pre>
<p>边界条件为：</p>
<ul>
<li><span>dp[0]=nums[0]                        // 只有一间房屋，则偷窃该房屋</span></li>
<li><span>dp[1]=max(nums[0],nums[1]) // 只有两间房屋，选择其中金额较高的房屋进行偷窃</span></li>
</ul>
<pre><code class="java language-java hljs"><span class="linenum hljs-number"> 1</span><span class="hljs-function"><span class="hljs-keyword">public</span>&nbsp;<span class="hljs-keyword">int</span>&nbsp;<span class="hljs-title">rob</span><span class="hljs-params">(<span class="hljs-keyword">int</span>[]&nbsp;nums)</span>&nbsp;</span>{<br><span class="linenum hljs-number"> 2</span>&nbsp;&nbsp;&nbsp;&nbsp;<span class="hljs-keyword">if</span>&nbsp;(nums&nbsp;==&nbsp;<span class="hljs-keyword">null</span>&nbsp;||&nbsp;nums.length&nbsp;==&nbsp;<span class="hljs-number">0</span>)&nbsp;{<br><span class="linenum hljs-number"> 3</span>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span class="hljs-keyword">return</span>&nbsp;<span class="hljs-number">0</span>;<br><span class="linenum hljs-number"> 4</span>&nbsp;&nbsp;&nbsp;&nbsp;}<br><span class="linenum hljs-number"> 5</span><br><span class="linenum hljs-number"> 6</span>&nbsp;&nbsp;&nbsp;&nbsp;<span class="hljs-keyword">if</span>&nbsp;(nums.length&nbsp;==&nbsp;<span class="hljs-number">1</span>)&nbsp;<span class="hljs-keyword">return</span>&nbsp;nums[<span class="hljs-number">0</span>];<br><span class="linenum hljs-number"> 7</span><br><span class="linenum hljs-number"> 8</span>&nbsp;&nbsp;&nbsp;&nbsp;<span class="hljs-keyword">int</span>[]&nbsp;dp&nbsp;=&nbsp;<span class="hljs-keyword">new</span>&nbsp;<span class="hljs-keyword">int</span>[nums.length];<br><span class="linenum hljs-number"> 9</span>&nbsp;&nbsp;&nbsp;&nbsp;dp[<span class="hljs-number">0</span>]&nbsp;=&nbsp;nums[<span class="hljs-number">0</span>];<br><span class="linenum hljs-number">10</span>&nbsp;&nbsp;&nbsp;&nbsp;dp[<span class="hljs-number">1</span>]&nbsp;=&nbsp;Math.max(nums[<span class="hljs-number">0</span>],&nbsp;nums[<span class="hljs-number">1</span>]);<br><span class="linenum hljs-number">11</span>&nbsp;&nbsp;&nbsp;&nbsp;<span class="hljs-keyword">for</span>&nbsp;(<span class="hljs-keyword">int</span>&nbsp;i&nbsp;=&nbsp;<span class="hljs-number">2</span>;&nbsp;i&nbsp;&lt;&nbsp;nums.length;&nbsp;i&nbsp;++)&nbsp;{<br><span class="linenum hljs-number">12</span>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;dp[i]&nbsp;=&nbsp;Math.max(dp[i&nbsp;-&nbsp;<span class="hljs-number">2</span>]&nbsp;+&nbsp;nums[i],&nbsp;dp[i-<span class="hljs-number">1</span>]);<br><span class="linenum hljs-number">13</span>&nbsp;&nbsp;&nbsp;&nbsp;}<br><span class="linenum hljs-number">14</span><br><span class="linenum hljs-number">15</span>&nbsp;&nbsp;&nbsp;&nbsp;<span class="hljs-keyword">return</span>&nbsp;dp[nums.length&nbsp;-&nbsp;<span class="hljs-number">1</span>];<br><span class="linenum hljs-number">16</span>}<br></code></pre>
<p>上面的方法用到了额外空间，使用变量去掉数组</p>
<pre><code class="java language-java hljs"><span class="linenum hljs-number"> 1</span><span class="hljs-function"><span class="hljs-keyword">public</span>&nbsp;<span class="hljs-keyword">int</span>&nbsp;<span class="hljs-title">rob</span><span class="hljs-params">(<span class="hljs-keyword">int</span>[]&nbsp;nums)</span>&nbsp;</span>{<br><span class="linenum hljs-number"> 2</span>&nbsp;&nbsp;&nbsp;&nbsp;<span class="hljs-keyword">if</span>&nbsp;(nums&nbsp;==&nbsp;<span class="hljs-keyword">null</span>&nbsp;||&nbsp;nums.length&nbsp;==&nbsp;<span class="hljs-number">0</span>)&nbsp;{<br><span class="linenum hljs-number"> 3</span>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span class="hljs-keyword">return</span>&nbsp;<span class="hljs-number">0</span>;<br><span class="linenum hljs-number"> 4</span>&nbsp;&nbsp;&nbsp;&nbsp;}<br><span class="linenum hljs-number"> 5</span><br><span class="linenum hljs-number"> 6</span>&nbsp;&nbsp;&nbsp;&nbsp;<span class="hljs-keyword">if</span>&nbsp;(nums.length&nbsp;==&nbsp;<span class="hljs-number">1</span>)&nbsp;<span class="hljs-keyword">return</span>&nbsp;nums[<span class="hljs-number">0</span>];<br><span class="linenum hljs-number"> 7</span><br><span class="linenum hljs-number"> 8</span>&nbsp;&nbsp;&nbsp;&nbsp;<span class="hljs-keyword">int</span>&nbsp;f&nbsp;=&nbsp;nums[<span class="hljs-number">0</span>],&nbsp;s&nbsp;=&nbsp;Math.max(nums[<span class="hljs-number">0</span>],&nbsp;nums[<span class="hljs-number">1</span>]),&nbsp;tmp;<br><span class="linenum hljs-number"> 9</span>&nbsp;&nbsp;&nbsp;&nbsp;<span class="hljs-keyword">for</span>&nbsp;(<span class="hljs-keyword">int</span>&nbsp;i&nbsp;=&nbsp;<span class="hljs-number">2</span>;&nbsp;i&nbsp;&lt;&nbsp;nums.length;&nbsp;i&nbsp;++)&nbsp;{<br><span class="linenum hljs-number">10</span>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;tmp&nbsp;=&nbsp;s;<br><span class="linenum hljs-number">11</span>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;s&nbsp;=&nbsp;Math.max(f&nbsp;+&nbsp;nums[i],&nbsp;s);<br><span class="linenum hljs-number">12</span>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;f&nbsp;=&nbsp;tmp;<br><span class="linenum hljs-number">13</span>&nbsp;&nbsp;&nbsp;&nbsp;}<br><span class="linenum hljs-number">14</span><br><span class="linenum hljs-number">15</span>&nbsp;&nbsp;&nbsp;&nbsp;<span class="hljs-keyword">return</span>&nbsp;s;<br><span class="linenum hljs-number">16</span>}<br></code></pre>
<h4 id="h3362httpsleetcodecncomproblemsuniquepaths"><span>3.3 <a href="https://leetcode-cn.com/problems/unique-paths/">62. 不同路径</a></span></h4>
<p>一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。</p>
<p>机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。</p>
<p>问总共有多少条不同的路径？</p>
<figure><img src="https://p9-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/a71e2278ea4e4ed39bb0da47d4de1244~tplv-k3u1fbpfcp-watermark.image" alt="" title=""><figcaption></figcaption></figure>
<p>例如，上图是一个7 x 3 的网格。有多少可能的路径？</p>
<p>示例 1:</p>
<p>输入: m = 3, n = 2<br>输出: 3<br>解释:<br>从左上角开始，总共有 3 条路径可以到达右下角。</p>
<ol>
<li><span>向右 -&gt; 向右 -&gt; 向下</span></li>
<li><span>向右 -&gt; 向下 -&gt; 向右</span></li>
<li>向下 -&gt; 向右 -&gt; 向右<br>示例 2:</li>
</ol>
<p>输入: m = 7, n = 3<br>输出: 28</p>
<p>提示：</p>
<p>1 &lt;= m, n &lt;= 100<br>题目数据保证答案小于等于 2 * 10 ^ 9</p>
<p><strong>分析：</strong></p>
<ol>
<li><strong>确定状态：</strong>我们使用<code>int[][] dp</code>来存储子问题的结果，<code>dp[i][j]</code>就是从<code>dp[0][0]</code>走到<code>dp[i][j]</code>的路径数</li>
<li><strong>确定状态转移方程：</strong>机器人只能往右或往下走，所以到<code>dp[i][j]</code>的路径数就是它上边和左边格子的路径数之和：<code>dp[i][j]=dp[i - 1][j] + dp[i][j - 1]</code></li>
<li><strong>确定边界条件：</strong>由于机器人只能往右或往下走，当 <code>i == 0</code> 或者<code>j == 0</code>时只有一条路径可走</li>
</ol>
<pre><code class="java language-java hljs"><span class="linenum hljs-number"> 1</span><span class="hljs-function"><span class="hljs-keyword">public</span>&nbsp;<span class="hljs-keyword">int</span>&nbsp;<span class="hljs-title">uniquePaths</span><span class="hljs-params">(<span class="hljs-keyword">int</span>&nbsp;m,&nbsp;<span class="hljs-keyword">int</span>&nbsp;n)</span>&nbsp;</span>{<br><span class="linenum hljs-number"> 2</span>&nbsp;&nbsp;&nbsp;&nbsp;<span class="hljs-comment">//&nbsp;m或n为1的时候只有一条路径</span><br><span class="linenum hljs-number"> 3</span>&nbsp;&nbsp;&nbsp;&nbsp;<span class="hljs-comment">//&nbsp;状态转移方程为res[i][j]&nbsp;=&nbsp;res[i&nbsp;-&nbsp;1][j]&nbsp;+&nbsp;res[i][j&nbsp;-&nbsp;1];</span><br><span class="linenum hljs-number"> 4</span><br><span class="linenum hljs-number"> 5</span>&nbsp;&nbsp;&nbsp;&nbsp;<span class="hljs-keyword">if</span>&nbsp;(m&nbsp;==&nbsp;<span class="hljs-number">1</span>&nbsp;||&nbsp;n&nbsp;==&nbsp;<span class="hljs-number">1</span>)&nbsp;<span class="hljs-keyword">return</span>&nbsp;<span class="hljs-number">1</span>;<br><span class="linenum hljs-number"> 6</span>&nbsp;&nbsp;&nbsp;&nbsp;<span class="hljs-keyword">int</span>[][]&nbsp;dp&nbsp;=&nbsp;<span class="hljs-keyword">new</span>&nbsp;<span class="hljs-keyword">int</span>[m][n];<br><span class="linenum hljs-number"> 7</span><br><span class="linenum hljs-number"> 8</span>&nbsp;&nbsp;&nbsp;&nbsp;<span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span>&nbsp;i&nbsp;=&nbsp;<span class="hljs-number">0</span>;&nbsp;i&nbsp;&lt;&nbsp;m;&nbsp;i&nbsp;++)&nbsp;{<br><span class="linenum hljs-number"> 9</span>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span class="hljs-keyword">for</span>&nbsp;(<span class="hljs-keyword">int</span>&nbsp;j&nbsp;=&nbsp;<span class="hljs-number">0</span>;&nbsp;j&nbsp;&lt;&nbsp;n;&nbsp;j&nbsp;++)&nbsp;{<br><span class="linenum hljs-number">10</span>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span class="hljs-keyword">if</span>&nbsp;(i&nbsp;==&nbsp;<span class="hljs-number">0</span>&nbsp;||&nbsp;j&nbsp;==&nbsp;<span class="hljs-number">0</span>)&nbsp;{<br><span class="linenum hljs-number">11</span>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;dp[i][j]&nbsp;=&nbsp;<span class="hljs-number">1</span>;<br><span class="linenum hljs-number">12</span>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;<span class="hljs-keyword">else</span>&nbsp;{<br><span class="linenum hljs-number">13</span>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;dp[i][j]&nbsp;=&nbsp;dp[i&nbsp;-&nbsp;<span class="hljs-number">1</span>][j]&nbsp;+&nbsp;dp[i][j&nbsp;-&nbsp;<span class="hljs-number">1</span>];<br><span class="linenum hljs-number">14</span>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}<br><span class="linenum hljs-number">15</span>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}<br><span class="linenum hljs-number">16</span>&nbsp;&nbsp;&nbsp;&nbsp;}<br><span class="linenum hljs-number">17</span><br><span class="linenum hljs-number">18</span>&nbsp;&nbsp;&nbsp;&nbsp;<span class="hljs-keyword">return</span>&nbsp;dp[m-<span class="hljs-number">1</span>][n-<span class="hljs-number">1</span>];<br><span class="linenum hljs-number">19</span>}<br></code></pre></div></div></body>
</html>